Pairings for beginners
Pairing Programming
トーラス
格子点の集合を$ A := n\lambda_1+m\lambda_2 | n, m \in Zとし、トーラス上の関数をfとする。
fは複素平面上の関数となり、$ f(z+\lambda) = f(z + n\lambda_1+m\lambda_2)=f(z), z \in C, \lambda \in Aが成立する。
つまり、トーラス上の関数fは任意のzを全て同じ値に移すことになる。
トーラス上の関数は$ \lambda_1, \lambda_2による複素平面上の二重周期関数
Weierstrassの$ \wp関数
$ \wp(z) := 1/z^2 + \Sigma_{\lambda := n\lambda_1 + m\lambda_2 \in A}(1/(z-\lambda)^2-1/\lambda^2)
トーラスについての二重周期関数で$ \wp(z+\lambda_i) = \wp(z)となる。
$ \wp関数を級数展開し、偶関数であることにより奇数項を除去し、微分し、右辺をzの正の巾の和だけで表現すると、Liouville（リウビル）の定理を用いて右辺が定数であることが示されるので最終的に以下のような関係式が成立する。
$ \wp'(z)^2 = 4\wp(z)^3 -20c_2\wp(z)-28c_4
$ E_A := {(x,y) | y^2 = 4x^3 -20c_2x - 28c_4} \cup \inftyという集合を考えると、トーラス上の点zに対して、
$ \phi:T_A \ni z \to (\wp(z), \wp'(z)) \in E_A
という1対1対応関係の写像を構成できる。z=0の時が$ \infty。
つまり、トーラス$ T_Aは2変数3次方程式の解の集合（楕円曲線）$ E_Aと同じ集合。幾何学的なトーラスを$ \phiにより代数的なものとして扱えるようになる。
さらに、トーラスと楕円極限の点が対応しているだけでなく、$ \phiは同型写像。（点の足し算が写像先の足し算に1対1対の対応をしている）
EC上の足し算は有限体上のbinary group operation (add, mul)
(x′, y′) ∈ E, then (x′, −y′) ∈ E (but is not distinct if y′ = 0)
E : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 のWeierestrass equationにおいて体の標数がnot 2 or 3の場合、short Weierstrass equationのE : y2 = x3 + ax + bに。
$ i^2 + 1 = 0において2次拡大体$ F_{q^2} = F_q(i)としてEC上を考えると$ E(F_{q^2})にはより多くの点が存在し$ E(F_q)はsubgroupになる。
楕円曲線の特異点 = singular pointでxとyに対する偏微分が同時に0になる。
partial derivativesが消える点がsingular pointと呼ばれ、$ 4a^3+27b^2=0である場合に起こる。
https://gyazo.com/53697463715ddacdf6e87ec65da0d418
affine points (n-space)をprojective space(n+1-space)で考え、(0:1:0)として無限遠点が現れる。Z=1をaffine平面として考える。
https://gyazo.com/150bc890a69f87372d4663bef64ac684
$ E: y^2 = x^3 + ax + bで$ x = X/Z, y = Y/Z(Zの次数は任意）を代入しhomogenise(projectify)することで、$ E_p: Y^2Z = X^3 + aXZ^2 + bZ^3が得られる。
例えば、$ x = X/Z^2, y = Y/Z^3を代入してprojective equationが$ Y^2 = X^3 + 4XZ^4 - Z^6の場合、無限遠点は$ O = ({\lambda}^2:{\lambda}^3:0) \in P^2(F_{41})。
射影平面についての導入的な話
中心点から出発するどの直線をもみな1点と見做すことで得られるのが射影空間
例えば原点を通る直線$ L_t: y = txの集合を$ P^1(R)（実1次元射影空間）。
同じ直線を表す$ t = b/a$ a \neq 0で(a,b)の組の集合を(a:b)（射影座標、斉次座標）と書くと、
$ P^1(R) = {(ab)|a,b \in R^2 (0,0)}となる。
2次元空間で1対1に対応する局所座標系を考えると、
$ \phi_2: U_2 \ni (X:Y:Z) \to k^2 \ni (X/Z, Y/Z)
逆写像は、
$ \phi^{-1}_2: (x:y:1) \to (x,y)
$ (x,y) \in k^2 | y^2 = x^3 + ax + bに無限遠点Oを追加した集合は、$ (X,Y,Z)\in P^2(k) | Y^2Z = X^3 + aXZ^2 + bZ^3。
Z=0とするとX=0になるので、$ (X:Y:Z) = (0:Y:0) = (0:1:0)が無限遠点
Affine addition, Affine doublingの公式 （実際の実装では計算コストが高いので使われない）
https://gyazo.com/6b06986356fd645c6ff4cf5566b7680a
ナイーブに実装しようとすると、
無限遠点であるか
.$ x_P = x_Qであるか
.$ y_P = -y_Qの場合、加算は無限遠点に。
.$ y_P = y_Q \neq 0の場合、point doubling formulasを利用する
など多くの条件分岐が必要になってしまうがEC群の位数はとても大きいのでspecial caseは無視できる。
足し算->(十数倍〜数十倍）->掛け算->（数十倍〜百倍以上）->割り算
楕円曲線上の点のスカラー倍で効率的なdouble-and-add algorithm ($ O({log_2}n))
例えば、スカラー倍数mの10 bit binary representationが m = (m_9,...,m_0) = (1,0,1,0,0,0,1,1,1,1)とするとthe second most significant bitのm_8からm_0まで9回doublingsを計算し、m_i = 1である5回additionsを計算することで、mPが計算できる。
160-bit field上に定義されたECと1248-bits finite fieldはほぼ同じセキュリティ。
Weierestrass modelはoptimalなcurve modelではない。
projective space computations
コストの高いfield inversionsを避けるためにprojective spaceで計算する。
例えば、
M: multiplications
S: squarings
I: inversions
とすると、I >= 80Mくらい
affine point doubling: 2M+2S+I
affine point addition: 2M+S+I
projective doubling: 5M+6S
projective addition: 12M+2S
Jacobi-quartic curve
$ J: v^2 = au^4 + du^2 + 1
Jacobi-quartics doubling: 2M + 5S
Jacobi-quartics addition: 6M + 4S
より早いgroup law computationのためのcurve modelとしては他にも、
Edwards curve
Hessian curves
Montgomery curves
Edwards curveだと加算と2倍算の公式が同じになり、3倍算の公式も存在する。
twisted edwards curve
.$ -x^2 + y^2 = 1 + dx^2y^2
以下のパラメータでcurveの種類が変わる。jubjubもtwisted edwards curve
有限体の位数：q
subgroupの位数：r
d
jubjubはモンゴメリ型にも変換可能
.$ y^2 = x^3 + Ax^2 + x
Tutorial of Twisted Edwards Curves in Elliptic Curve Cryptography
$ P(x_1, y_1), Q(x_2, y_2)のtwisted edwards curveでの加法公式
https://gyazo.com/86bf195b9a981204587540157f014a75
Torsion
$ E(F_q)は以下のいずれか
それ自体が巡回群 (better)
2つの巡回群積の同型写像 ($ Z_{n_1} \times Z_{n_2}において$ n_1はできるだけ小さいようにする）
群の位数 (group order)：群の元の数
元の位数(point of order)：群のある元を生成元として有限部分巡回群が作れるとき、その部分巡回群の位数。
つまり、the non-trivial subgroup （非自明な部分群）
ラグランジェの定理：群Gの部分群の位数は、Gの位数の約数になる。
例えば、#E(F_q) = 105 = 3*5*7の場合、curve上の点の位数(とsubgroup)は{1, 3, 5, 7, 15, 21, 35, 105}のいずれかになる。
cofactor = (群の位数）/ (元の位数）
ある元の位数を持つcurve上の点を得たい場合はgenerator pointにcofactorをかければOK
generator pointに群の位数をかけるとkilledされ無限遠点に送られる。
r-torsion: rでkillされる点
代数的閉包(algebraic closure), 代数的閉体(algebraically closed field)
y^2 = x^3 + ax + bを満たす(x,y)は$ C複素数全体や位数が2か3ではない有限体の代数的閉体で考える。
代数的閉体とはその中で任意の多項式が因数分解できるもの
例えば、実数全体は$ x^2 + 1では因数分解できないので代数的閉体ではない。
実数に$ \sqrt{-1} を追加したものが複素数全体
有限体にも元を追加していくことで代数的閉体にできる。
複素数全体が代数的閉体とは任意の多項式が因数分解できること
Is it safe to operate over the prime sub-group of Curve25519?
スカラー値を0 mod 8のみにする。つまり、3番目までのLSBを全てゼロにする。
Ed25519では公開鍵がlow orderであるかどうかはチェックせず、秘密鍵が8の倍数であるようにすることで、その秘密鍵にlow order pointを乗算した時にOになるようにしている。なので、DH鍵交換で一方のパーティーがsmall order pointを乗算するとsecret shareは0になる。
Generator pointに欲しい位数のsubgroupのcofactorを乗算するとそのsubgroup上の点が得られ、cofactorが8の時は点に8を乗算することでその点がorder {8, 4, 2, 1}の場合はkilledされ無限遠点になる。逆に素数群上であれば8をかけてもゼロにはならない。これらは、楕円曲線上の点に対してその群の位数をかけると無限遠点に飛ばされる性質を利用している。
楕円曲線暗号の256bitがRSAの3072bitと同等のセキュリティであり速度と安全性のバランスが取れているので256bit程度のprime fieldで実装されることが多い。
ed25519のpython実装を紐解く その１数学編
prime order subgroup
中国剰余定理
0~m_1m_2の間に$ x \equiv b_1 (mod m_1), x \equiv b_2 (mod m_2)となるような整数x＝rがただ1つ存在するとき、$ x \equiv r (mod m_1m_2)が成立する。
ECDLPの攻撃ベクタは楕円曲線の最も大きな素数subgroupのサイズに依存するので群の位数はできるだけ素数に近くなるようにすべき。
例えば、[k]P = QのECDLPを攻撃するためにはナイーブにはMAX位数回分、繰り返しかけてi=kとなるようなiを見つけること。
それよりも、適切なcofactorをかけてそれぞれのprime order subgroupにマップし、そのsubgroup位数内でかけて解くことができる。群の位数に対して元の位数が大きくなるほどcofactorが大きくなる。
例えば、subgroupの位数が966 = 2 * 3 * 7 * 23の時、2, 3, 7, 23
例えば、$ P_{23} = (966/23)P = 42P = (890, 665), Q_{23} = 42Q = (68, 281)で、j=23の時のsubgroupのgenerator pointを求め、$ k_{23} \in {1,...,22}, Q_{23} = k_{23}P_{23}となるような$ k_{23}を繰り返し計算して求め、$ k_{23} = 20で成り立つことがわかる。
これをそれぞれに対して行い中国剰余定理を用いることでk=687が求まり、j=23が計算のボトルネックになっていることがわかる。
Hasse bound
群の位数は有限体の位数をqとすると、$ q+1-2\sqrt{q}, q + 1 + 2\sqrt{q}の間に存在する。
Frobenius endomorphism
フロベニウス自己準同型
楕円曲線の自己準同型
フロベニウス写像を$ \piとして有限体の位数をqとすると、
$ \pi: E \to E, (x,y) \to (x^q, y^q)
つまり、iff $ \pi(P) = PのときにPは楕円曲線上の点になる。
要は、楕円曲線上の点のx、y座標をそれぞれ有限体巾乗すると元の点に移る。
フロベニウス自己準同型の特性多項式
$ \sigma^2 -t\sigma + q = 0
$ tをフロベニウス自己準同型写像のトレースと呼ぶ。また、 t = (q+1) - # E(F_q)
半群：単位元や逆元が定義されず結合法則を満たす演算のみを定義
モノイド：結合法則を満たす演算と単位元を定義
単位元を持つ半群であり、逆元の条件を外した群
環：加法についてアーベル群、結合法則を満たす乗法、加法と乗法に関する分配法則
加法についてアーベル群、乗法について半群
自己準同型環：
Schoof''s polynomial-time algorithm
GLV/GLS techniques
バイナリ法：$ g^a (modp)を高速に求める計算アルゴリズム。
.$ O(log(p))で計算できるので有限体の逆数の求め方としてFermatの小定理は拡張Euclidの互除法と同程度の計算量になる。
実数体に$ iを加えて複素数体（二次拡大体）できるのと同様に有限体に対しても拡大体を作る。
複素数体は代数的閉包であり複素数係数のどんな多項式も一次式の積に因数分解できる。
例えば、$ f(t) = t^2 + 1において$ f(i) = 0とすると、
.$ f(t) = (t+2)(t-2)mod5なので$ F_5に$ iを追加しても拡大体にはならない（すでに$ iが含まれている）
.$ f(t)は$ F_7上既約（$ t^2+1=0が$ F_7で解けない、$ t^2+1が因数分解できない）なので、$ F_7に$ iを追加すると二次拡大体$ F_{7^2}になる
ベクトル空間は体におけるスカラー積の演算が外部算法（他の集合の元との演算）である構造。
よって、体$ Fの拡大体$ Eは$ F上のベクトル空間
F上の多項式：多項式の係数が体Fに含まれる数。解がなす体は係数体の拡大体となることが多い。代数学の基本定理より複素数体まで拡大すればn次方程式においてn個全ての解が見つかる。
つまり、体F上のn方程式がF上に全ての解を持つとき、一次式の積の形に式変形することができ「F上で因数分解可能である」と言える。
これは解の存在性を保証するだけで代数的に解けるかどうかはガロア理論。
「体F上の方程式が解けるかどうか」と「FとCの間の方程式の解を全て含む体にFをうまく拡大することができるか」という問題が同値。
Divisor
楕円曲線上のdivisor Dはcurve上の点の有限和。
$ D = \Sigma_{P \in E(\overline{F_q})}n_p(P)
curveの零点(zeroes)と関数の極(poles)の関係性を定義する。
zeroes: x軸と接する点
零点での位数はx軸と何重に接しているか
poles: 無限遠点
極での位数は$ f(x) =~ c(x-a)^nで$ ord_a(f) := -n
位数の性質
.$ ord_a(f) = - ord_a(1/f)
関数fがx=aで位数nの零点を持つなら関数1/fはx=aで位数nの極を持つ
.$ ord_a(fg) = ord_a(f) + ord_a(g)
2つの関数の積の位数はそれぞれの関数の位数の和になる
2つの関数の和の位数は小さい方の位数になる。
$ E \ni P = (x, y) \to yというE上の点P＝(x, y) に対してそのy座標を返す関数を考えると零点の位数は1になり、極の位数は-3になる。
楕円曲線上の主因子(principal divisor)の性質
ある関数fが点P_iで位数n_iの零点、点Q_jで位数m_jの極を持っているとき、
$ div(f) := \Sigma_in_i(P_i) - \Sigma_jm_j(Q_j)
例えば、楕円曲線上の関数yに対応する因子は、
$ div(y) = (P_1) + (P_2) + (P_3) - 3(O)
https://gyazo.com/f2a54834dad59ecedda3c0346b429edb
$ div(f) = \Sigma_in_i(P_i)とすると以下が成り立つ。
$ \Sigma_in_i = 0
$ \Sigma_in_iP_i=O
つまり、関数の零点や極がn個ある時、n-1個の点の位置を決めると、残りの位置が一意に決まる。
通常の楕円曲線はgenus(種数）が１でトーラスの穴が一つ。
genus=1の場合はdivisorクラスのピカール群 $ Pic^0(E)と楕円曲線上の点は一対一対応
Weil reciprocity （Weil相互法則）
楕円曲線上の関数f, gに対して、principal divisorをdiv(f), div(g)として、$ f(div(g))=g(div(f))が成立する。（f,g はnon-zeroなので無限遠点をサポートしない）
pairing groups
暗号学的ペアリング：楕円曲線上で定義される非退化双線形写像
P, Qは同じprime orderの巡回群の素集合系。素集合系出ないとweil reciprocityを利用できず、P,Qが同じ集合だとdivisorが衝突してしまう。
bilinear map
$ e: G_1 \times G_2 \to G_T
$ G_1, G_2はk次拡大体上の楕円曲線$ E(F_{q^k})、ターゲットグループの$ G_Tは乗法群$ F^*_{q^k}の元
https://gyazo.com/25aadcd4b755a6ced655afc980125b5d
https://gyazo.com/81e331029a02c54437aac9aca08a1306
非退化：$ e(P, Q) \neq 1でP, Qはnon-trivial
P, Qは互いに素集合で同じ素数位数rのsubgroup上である必要。Pの最小拡大体がQ。
代数的閉包の位数rのr-tortionをE[r)とすると、
https://gyazo.com/9c057d18c700fd7f9ca6d521971e06d7
位数は$ r^2であり、全ての位数rのsubgroupは無限遠点でoverlapしているので、$ r-torsionは位数rのr+1個subgroupから成る。
また、点Pに置けるtrace mapは以下のように定義。$ \piがq-powerのフロベニウス準同型で、ガオス理論より$ Tr: E(F_{q^k}) \to E(F_q)
https://gyazo.com/6cce5a445154909983d6339bbfc050b9
$ (q^k-1) mod7 = 0となる最小のkはk=3なので、$ u^3 + u + 4 = 0として$ F_{q^3} = F_q(u)。7-torsionはこの３次拡大体のcurveに含まれている。7-torsionは下図のように49点あり、位数7の8個のsubgroupから成る。
curve上のtrace mapは$ Tr(P) = (x,y) + (x^q,y^q) + (x^{q^2},y^{q^2})
https://gyazo.com/8b5bee65e1e59a688fc62c1d39873cbe
torsion subgroupにおいてはフロベニウス準同型はtrivialなのでtrace mapはkの乗算として作用する。$ Tr(P) = [k)P。さらに、Trはtorsion内に移す。
$ F_q上に定義されたr-torion内の位数rのsubgroupが存在。-> base-field subgroup $ g_1
フロベニウス準同型は$ g_1上だけでtrivialなので（$ \pi(P) = P）
https://gyazo.com/de9a1f8146763997d351a24fad07c14d
同様に、Tr(P) = Oとなるtrace zero subgroupを定義できる。
https://gyazo.com/4d5d5cdb2a2e5b7970c08ed435367f7d
https://gyazo.com/acd7f1ad82b2991882fc5bc497dc7f65
#$ E(F_q) = q+1の時その楕円曲線をsupersingularと呼び、$ E(F_q)から$ E(F_{q^k}へのdistortion mapを持っている。（singularとnon-singularなcurveとは関係なし）
distortion mapは常に他のsubgroupに写像する訳ではない。$ g_1へはtrace map、$ g_2へはanti_trace mapを用いて移すことができる。
https://gyazo.com/095118e59b787cb7d28afa07a0fe9f1f
distortion写像
楕円曲線上のある点Pの巡回群$ {P} := {nP | n \in Z }に含まれない別の点Qに移す線形写像$ \phi
線形写像なので整数aに対して、
$ \phi(aP) = a\phi(P) = aQ
Pairing types
$ G_2の定義によって異なる。
https://gyazo.com/486e4b3ddf7a32b4ceced198cc1535bf
type 1:
Eがsupersingularなので$ g_1はdistortion mapを持つ。G_1=G_2 = g_1として、
$ e(P, Q) = e'(P, \phi(Q))が成り立つ
以下のEは全てordinary curve
type2:
G2はg_1とg_2以外のsubgroupに存在し、G_2 -> G_1 のtrace mapと効率性のためG_2 -> g_2のanti-trace mapを持つ。
欠点は、G2へのハッシュやrandom element生成の方法がない
type3:
$ G_2 = g_2のパターンでanti-trace mapにより代数的閉包上でのcofactor乗算でG2へのハッシュが可能。最新のpairingは基本的にこれ。
type4:
G2がr-torion全体のパターン。G2へのハッシュは可能だが効率的ではない。
Twisted curves
G2への効率的なハッシュが可能に。
twisted curveへの同型逆写像が存在し、base fieldへ移す。なので、G2での２次拡大体上での演算を行う代わりにtwisted curveへ移し、base fieldで演算し、その結果を同型写像で戻すことが可能。
https://gyazo.com/d00fba8c81dba2ae9adc8cef92ea15a6
embedding degreeがk=12でd=6であれば12次ではなく2次で演算することができるのでtwistのdegreeは大きい方が望ましい。（d=6が最大）
The Weil pairing
https://gyazo.com/9a072eeafc7129f19d74f14d41143a48
楕円曲線上の２つのr-torion点P, Qに基づく因子の決定（アーベル・ヤコビの定理を満たす）
ペアリングは因子の選び方に影響を与えない
その因子に基づく関数f, gの決定
weil pairingの決定
Pがr-totion点であれば以下のようなDivisorを持つ関数が存在。
https://gyazo.com/76d5233050cf8e5d2c3d830fd8fd9b71
無限遠点を含まないようにG2上のランダムな２点をピックアップ。（pairing結果はこの2点によらない）
$ D_P = (P+R)-(R), D_Q=(Q+S)-(S)
https://gyazo.com/312a3c458153410d25d4f03b3109ba1a
The Tate pairing
Miller's algorithm
アーベルヤコビの定理を満たす因子Dが与えられた時、(f) = Dなる関数fを効率的に計算するアルゴリズム。O(r)がO(logr)に。
BKLS-GHSアルゴリズムによりDivisor評価の代わりにCurve上の点で評価を可能にすることで2点評価から1点評価に。
Iterationごとに評価処理を行うので結構でかい。
Birational equivalence vs Isomorphic
Isomorphic
同型、
「同じ」楕円曲線と表現できる。
https://gyazo.com/7389ab6c21c3578093fa47e79cd6fb15
像を多項式のタプルで表現。逆像も。
Birational equivalence
「ほぼ同じ」楕円曲線と表現できる。
一部のとても小さな例外が存在
https://gyazo.com/3bb3d00863fcc06a7f7d8b827aea5594
具体的には$ f_2(x,y) = 0, g_2(x,y)=0にはならない。
逆像も同じように定義。
https://gyazo.com/dae136b06996a9615c404fba77676266
edwards curve -> twisted edwards curveへの写像は$ \phi(x,y) = (ix, y)で定義されるので同型。
edwards curve -> mongomeryはBirational equivalence
Kalinski Modular inverse algorithm.
Refs
Pairing の計算法とその実装
High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves
Handbook of Applied Cryptography - Efficient Implementation
BLS署名における双線形性（ペアリング）について